1. Field of the Invention
The invention relates to data processor systems utilizing parallel processors in distinct phases of operations with restoring structures so that the time sequence of data groups are preserved or restored.
2. Prior Development Considerations
An aspect of current computers involves bundling data into packets, sets or groups and somewhat discretely processing the data so bundled. In general, the present development is based on recognizing the significance of the temporal priority of bundled data packets and preserving or restoring that priority, particularly as related to systems wherein processing operations for different data sets may vary.
In general, the disclosed embodiments take the form of parallel processor systems. As an example for discussing such systems in greater detail, a computer graphics system is treated below. Generally, some preliminary consideration of computer graphics systems is deemed appropriate.
Perhaps video games are the best known form of computer graphics systems. However, the technology involves a considerable number of other forms of display apparatus as for training, designing, modelling and so on. Typically these systems give the viewer the impression of looking at a television set, or through a window at a scene. In graphics terminology, the window is called a "viewport". The creation of a scene in a viewport from primitive object data involves several individual processing operations as generally well known in the art. That is, scenes are created in a viewport from primitive geometric or object data with respect to a specific viewpoint.
At the outset, a computer graphics system must traverse a data structure in a central processor and select the object data that is relevant to a scene. Primitive object data may embrace objects, polygons or lines. The selected object data for a scene is transformed into a convenient coordinate system where it can be compared to the viewport. Such comparison enables the data to be clipped so that those parts of objects that lie outside the viewport are cut away.
After the object data for a scene is defined for a specific viewpoint, it is scan converted, specifically it is changed from a set of vertices with connectivity information implying lines and surfaces, to a list of picture elements (pixels) that can be processed to depict lines and surfaces. In the iterative treatment of primitives (object data) cumulative frame buffer pixels (representing a picture) are stored in the frame buffer to be further supplemented or updated for dynamic displays by update pixels. In the initial operations, pixels also may be preliminarily shaded, specifically, color determinations are indicated.
In processing pixels, the visibility of object surfaces is determined for each pixel. Generally, only the closest surface to the viewer should be visible as represented by each pixel in a display. The most common algorithm used to omit hidden surfaces involves the so called "Z buffer". Each pixel is assigned a Z value that indicates the distance from a specific object surface location to a viewpoint. Essentially, Z values of the dissected surfaces are compared and of all the surface locations contending for presence in a pixel, the one that is closest to the viewpoint is stored in the frame buffer for the display. Data representing other surfaces is discarded. Numerous visibility algorithms exist, as for instance see U.S. Pat. No. 4,918,626, entitled COMPUTER GRAPHICS PRIORITY SYSTEM WITH ANTIALIASING, issued Apr. 17, 1990, to Gary S. Watkins, Glen A. Eckart and Russell A. Brown.
To improve the appearance of displays, another pixel processing operation involves blending pixels. That is, to avoid jagged lines or edges and accommodate transparency, the representations of two surfaces that contend for presence in a pixel are blended.
For the generation of a picture, frame buffer pixels are reformatted and provided in a raster pattern to drive a display unit, e.g. a cathode ray (CRT) apparatus. For a dynamic display, the frame buffer is cyclically updated or refreshed by blending update pixels with frame buffer pixels to reflect a changing scene.
The operations attendant the steps as explained above involve vast amounts of computation. For example, a scene may be composed from hundreds of thousands of polygons each of which must be processed with its presence reflected in individual display pixels. As is the case in much of the field of computer engineering, one trick to make computations run fast involves parallelism. In that regard, in various applications within the computer field, it has been proposed to variously partition computations among parallel processors. However, in computer graphics, partitioning computations for parallel operation presents certain difficulties. To be somewhat specific, data from a host computer relates to both primitives and state. Generally, primitives indicate what is to be drawn, while state indicates how things are to be drawn. State tends to be appropriate for a temporal series of primitives. Therefore, if the primitive order is changed, state is likely to be erroneously affected. Also, the order of primitives in and of themselves may be important.
The system of the present invention is based on recognizing the importance of preserving a time sequence, or temporal priority for data in computation as it passes through processors. Broadly, the system of the present invention is a processing system utilizing parallel processors with the preserved time sequence of data, that is, preserved or restored temporal priority.